import java.util.*;

/**
 * @author LKQ
 * @date 2022/6/15 9:20
 * @description 排序 + 二分查找 + 双指针
 */
public class Solution3 {
    public static void main(String[] args) {

    }
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length, left = 0, right = nums[n - 1] - nums[0];
        while (left <= right) {
            int mid = (left + right) / 2;
            int cnt = 0;
            // 利用双指针查找 <= mid 的数对数量
            for (int i = 0, j = 0; j < n; j++) {
                while (nums[j] - nums[i] > mid) {
                    i++;
                }
                cnt += j - i;
            }
            if (cnt >= k) {
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        return left;
    }
}
